<!DOCTYPE html>
<html lang="en">
    <head>
    <title>Greedy Algo: Jump Game - Tinusgraglin</title>
    
    
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1"><meta name="description" content="A Slice Greedy Algo: Jump Game My attack on the jump game problem."/><meta name="keywords" content="algo, greedy-algo" />
    <meta property="og:title" content="A Slice of Tgl -&nbsp;Greedy Algo: Jump Game" />
    <meta property="og:type" content="website"/><meta property="og:url" content="&#x2F;blog&#x2F;jump-game&#x2F;"/><meta property="og:description" content="My attack on the jump game problem."/>
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Regular.woff2" as="font" type="font/woff2" crossorigin="anonymous">
    <link rel="preload" href="/blog/assets/fonts/FiraCode-Bold.woff2" as="font" type="font/woff2" crossorigin="anonymous">

    <link rel="stylesheet" href="/blog/style.css?h=97e262212a0704163528">
    <link rel="stylesheet" href=" /blog/color/orange.css?h=a5a5d7faf9d4bc3e0b18">
    

  

  <link rel="stylesheet" href="/blog/assets/katex/katex.min.css">

  <script defer type="text/javascript" src="/blog/assets/katex/katex.min.js"></script>
  <script defer type="text/javascript" src="/blog/assets/katex/mathtex-script-type.min.js"></script>

  <script defer src="/blog/assets/katex/auto-render.min.js"
    onload="renderMathInElement(document.body, {
				delimiters: [
					{left: '$$', right: '$$', display: true},
					{left: '$', right: '$', display: false},
					{left: '\\(', right: '\\)', display: false},
					{left: '\\[', right: '\\]', display: true}
				]
			});"></script>


  </head>
    <body>
        <div class="container center">
<header class="header">
    <div class="header__inner">
        <div class="header__logo">
            <a href="&#x2F;blog">
    <div class="logo">
        LIN
    </div>
</a>
        </div>
        <div class="menu-trigger">menu</div>
    </div>
    
    <nav class="menu">
        <ul class="menu__inner menu__inner--desktop">
            
            
                    <li>
                        <a href="
    
        /blog/about
    
">about</a>
                    </li>
                
            </ul>

        <ul class="menu__inner menu__inner--mobile">
            
        <li>
            <a href="
    
        /blog/about
    
">about</a>
        </li>
        </ul>
    </nav>

    </header>
<div class="content"><article class="post">
        <header>
            <h1 class="post-title">
                <a href="&#x2F;blog&#x2F;jump-game&#x2F;">Greedy Algo: Jump Game</a>
            </h1>
            
    <div class="post-meta">
        <span class="post-date">2022.10.01
                </span>

        <span class="post-author"></span>

        

    
    :: {<a href="/blog/categories/algo/">algo</a>} 

            
    ::
    #<a href="/blog/tags/greedy-algo/">greedy-algo</a>
        
    
            
        
    </div>

            
    
</header><h1 id="jump-game">Jump Game<a class="zola-anchor" href="#jump-game" aria-label="Anchor link for: jump-game">§</a>
</h1>
<p>$S=a_1,a_2,\cdots,a_n$</p>
<p>From left to right, when on $a_i$ ($1\le i&lt;n$), if $i+a_i\ge n-1$ so we can jump directly to the end, then just jump to the end, otherwise, jump right $j\in[1,a_i]$ units onto $a_{i+j}$ so that $j+a_{i+j}$ is maximized:</p>
<p>$$\begin{aligned}\max_j\ j+a_{i+j} \cr \text{s.t.} \ {j\in[1,a_i]}\end{aligned}$$</p>
<p>Suppose the sequence of all the jump distances sequentially chosen by the algorithm is denoted by $P=j_1,j_2,\cdots,j_k$ such that $\sum_{i=1}^k j_i=n-1$. Now we <strong>assume that $P$ is not optimal</strong>, and let $Q=g_1,g_2,\cdots,g_m$ be the sequence of jump distance of one of the optimal solutions <strong>that has the longest common prefix with</strong> $P$ such that $m&lt;k$ and $\sum_{i=1}^m g_i=n-1$. We put them together below:</p>
<p>$$\begin{aligned}&amp;P=j_1,j_2,\cdots,j_m,\cdots,j_k\cr &amp;Q=g_1,g_2,\cdots,g_m\end{aligned}$$</p>
<p>We compare $P$ and $Q$ from left to right, and assume that they start to differ after the $p$ elements where $0\le p&lt;m$. Thus they agree on the first $p$ element(s), but differ at the $(p+1)$-th.</p>
<p>If $p=m-1$, then after $m-1$ jumps $j_1(g_1),j_2(g_2),\cdots,j_{m-1}(g_{m-1})$, the optimal answer $Q$ suggests that we can jump right $g_m$ units directly to the end, which the greedy algorithm will definitely choose to do and terminates itself afterwards and thus we will have $k=m$, a contradiction to the previous statement $m&lt;k$. Thus in this case, we can conclude that $P$ must be optimal.</p>
<p>Otherwise, if $p&lt;m-1$, then there are at least two moves after $g_p$ in $Q$:</p>
<p>$$\begin{aligned}&amp;P=j_1,\cdots,j_p,j_{p+1},j_{p+2}\cdots,j_m,\cdots,j_k\cr &amp;Q=g_1,\cdots,g_p,g_{p+1},g_{p+2}\cdots,g_m\end{aligned}$$</p>
<p>Let $r=1+\sum_{i=1}^pj_p=1+\sum_{i=1}^pg_p$ be the index of element in $S$ we land on after the first $p$ jumps, then we argue that</p>
<p>$$g_{p+1}+g_{p+2}\in [j_{p+1},j_{p+1}+a_{r+j_{p+1}}]$$</p>
<p>so that we can generate another sequence $R$ from $Q$ by replacing $g_{p+1},g_{p+2}$ with $j_{p+1},k_{p+2}$ where $k_{p+2}=g_{p+1}+g_{p+2}-j_{p+1}\le a_{r+j_{p+1}}$ and we claim that $R$ is a valid solution to the original problem and in fact, is also an optimal one. To see this, note that</p>
<ol>
<li>$g_1,\cdots,g_{p}$ ($j_1,\cdots,j_{p}$) are clearly valid.</li>
<li>$j_{p+1}$ is a valid move since it is generated by the algorithm.</li>
<li>$k_{p+2}$ is also valid since $k_{p+2}\le a_{r+j_{p+1}}$.</li>
<li>Since $g_{p+1}+g_{p+2}=j_{p+1}+k_{p+2}$, we arrive at the same position before continuing with $g_{p+2},\cdots,g_m$, all of which are valid moves.</li>
<li>$\sum_{i=1}^m R[i]=n-1$.</li>
</ol>
<p>And since $|R|=|Q|$, $R$ is also an optimal solution. Now here comes the contradiction: $R$ has a longer common prefix with $P$ than $Q$: $g_1,\cdots,g_p,j_{p+1}$, which contradicts the definition of $Q$. And thus, we can conclude that $P$ must be optimal.</p>
<p>The proof of $g_{p+1}+g_{p+2}\in [j_{p+1},j_{p+1}+a_{r+j_{p+1}}]$ is a bit of lengthy, we demonstrate the basic idea with a picture here:</p>


        
    

        
        
    </article></div>
    <div class="pagination">
        <div class="pagination__buttons">
            </div>
    </div>
<footer class="footer">
                    <div class="footer__inner"><div class="copyright">
            <span>© 2024 Tinusgraglin <span/>
            <span>:: Powered by <a href="https://www.getzola.org/">Zola</a>(<a href="https://www.rust-lang.org/">Rust</a>) and <a href="https://bun.sh">Bun</a>(<a href="https://ziglang.org">Zig</a>)</span>
        </div>
    <script type="text/javascript" src="/blog/assets/js/main.js"></script>
</div>
                    

                </footer></div>
    </body>
</html>
